package week_05.sort;

import java.util.ArrayList;
import java.util.List;

public class HeapSort implements Sort {
    @Override
    public String toString() {
        return "HeapSort::";
    }

    @Override
    public void sort(int[] nums) {
        for (int item : nums) {
            add(item);
        }
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            nums[i] = poll();
        }
    }


    private List<Integer> heap = new ArrayList<>();

    // 实现堆排序  使用数组实现 从0开始
    // 插入节点
    public void add(int val) {
        heap.add(val);
        //向上调节堆
        heapifyUp(heap.size() - 1);
    }

    private void heapifyUp(int c) {
        while (c > 0) {
            int p = (c - 1) / 2;
            if (heap.get(c) < heap.get(p)) {
                swap(p, c);
            } else break;
            c = p;
        }
    }

    private void swap(int i, int j) {
        int tmp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, tmp);

    }

    // 弹出堆顶
    public int poll() {
        if (heap.size() == 0) throw new RuntimeException();
        int top = heap.get(0);
        swap(0, heap.size() - 1);
        heap.remove(heap.size() - 1);
        heapifyDown(0);
        return top;
    }


    private void heapifyDown(int p) {
        int c = 2 * p + 1;
        while (c < heap.size()) {
            int c2 = 2 * p + 2;
            if (c2 < heap.size() && heap.get(c2) < heap.get(c)) {
                c = c2;
            }
            if (c < heap.size() && heap.get(c) < heap.get(p)) {
                swap(p, c);
            } else break;
            p = c;
            c = 2 * p + 1;

        }

    }
}
